/**
 * Created by L.jp
 * Description:给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
 * 例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
 * 例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
 * User: 86189
 * Date: 2022-09-04
 * Time: 11:31
 */
public class Solution {
    public int longestValidParentheses (String s) {
        if(s.length()==0){
            return 0;
        }
        int n=s.length();
        //定义状态，dp[i]表示s字符串以i结尾的位置的最长有效括号的长度
        int[] dp=new int[n];
        int max=0;
        //不管第一个字符是左括号还是右括号，第一个位置的有效括号长度都是0，所以从第二个字符的位置开始计算
        for(int i=1;i<n;i++){
            //如果当前字符是')',那么就要找到左括号的位置，就是利用前一个最长有效括号长度长，即i-dp[i-1]-1就是左括号下标
            if(s.charAt(i)==')'){
                //如果当前字符是右括号，前一个是左括号。那么就把以前两个字符结尾的最长有效长度再加上自己的一对括号长度即dp[i-2]+2
                if(s.charAt(i-1)=='('){
                    dp[i]=(i>=2 ? dp[i-2] : 0)+2;
                }else if(i-dp[i-1]>0 && s.charAt(i-dp[i-1]-1)=='('){ //如果当前字符是右括号，前一个也是右括号
                    //那么就要找到与之匹配的左括号，下标就是i-dp[i-1]-1
                    //如果找到了左括号，那么当前位置的最长有效括号的长度就要在前一个最长有效长度的基础上加上自己的一对括号，就是dp[i-1]+2
                    //但是依然还有可能这个匹配的左括号前面还有合法的括号序列，所以也要考虑，就要看左括号前面一个字符下标i-dp[i-1]-2是否合法,
                    //如果合法，那么就要加上左括号前面一个字符所拥有的最长有效括号的长度就是dp[i-dp[i-1]-2]
                    dp[i]=2+dp[i-1]+(i-dp[i-1]-2 > -1 ? dp[i-dp[i-1]-2] : 0);
                }
            }
            //更新最终的长度
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}
